"""
插入排序：O(n^2)
"""


def insertion_sort(sequence):
    for index in range(1, len(sequence)):
        while index > 0 and sequence[index-1] > sequence[index]:
            sequence[index], sequence[index-1] = sequence[index-1], sequence[index]
            index = index - 1
    return sequence


if __name__ == '__main__':
    sequence = [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    print(sequence)
    print(insertion_sort(sequence))
